//
// Description: 6010. 完成旅途的最少时间
// Created by Loading on 2022/2/28.
//

#include <bits/stdc++.h>

using namespace std;

long long minimumTime(vector<int> &time, int totalTrips) {
    sort(time.begin(), time.end());

    // 判断当前时间是否满足旅途
    auto check = [&](long long mid) {
        long long cnt = 0;
        for (auto x : time) {
            if (mid / x == 0) {
                break;
            }
            cnt += mid / x;
            if (cnt >= totalTrips) {
                return true;
            }
        }
        return false;
    };

    long long l = time[0], r = (long long) totalTrips * time[0];
    // 二分时间
    while (l < r) {
        long long mid = l + (r - l >> 1);
        if (check(mid)) {
            r = mid;    // check()判断mid是否满足性质
        } else {
            l = mid + 1;
        }
    }

    return l;
}

int main() {
    vector<int> time = {1, 2, 3};
    int totalTrips = 5;
    auto res = minimumTime(time, totalTrips);
    cout << res << endl;

    return 0;
}